<?php
/*
 * Check if array contains three numbers that add up to 0
 * A better solution than iterate through every combination:
 * loop i=0 k=length-1 j=i+1
 * for i=0 to i=length-1:
 * 1) a[i] + a[k] + a[j] = sum = 0 => Match!
 * 2) sum > 0 => too big, k--
 * 3) sum < 0 => too small, j++
*/

require_once 'util.php';

$sample = generateRandomArray(-10, 10, 10);
// Sort array
quick_sort( $sample );

var_dump( $sample );

testArrayThreeSum($sample);

function testArrayThreeSum( $sample ){
	$length = count( $sample );

	// At least should contain 3 elements
	if( $length < 3 ){
		echo "Array too short";
		return false;
	}



	// At least 1 positive number and 1 negative number
	if( ($sample[0] * $sample[$length-1]) > 0 ){
		echo "Array too short";
		return false;
	}

	// Start looping
	$i = 0;
	$j = 1;
	$k = $length - 1;
	while( $i < $k ){
		$j = $i + 1;
		$k = $length - 1;
		while( $j < $k ){
			$sum = $sample[$i] + $sample[$j] + $sample[$k];
			if( $sum == 0 ){
				// Found!!!
				echo "$sample[$i] + $sample[$j] + $sample[$k] is 0!!!<br/>";
				return true;
			}
			else if( 0 > $sum ){
				// Too small
				$j++;
			}
			else if( 0 < $sum ){
				$k--;
			}
		}
		// $j and $k collided, search is done for current $i
		$i++;
	}

	echo "Not found!";
	return false;

}